FPGAs may be used to implement large systems that include millions of gates and megabits of embedded memory. Of the tasks required in managing and optimizing a design, placement of components on the FPGAs and routing connections between components on the FPGA utilizing available resources can be the most challenging and time consuming. In order to satisfy placement and timing specifications, several iterations are often required to determine how components are to be placed on the target device and which routing resources to allocate to the components. The complexity of large systems often requires the use of EDA tools to manage and optimize their design onto physical target devices. Automated placement and routing algorithms in EDA tools perform the time consuming task of placement and routing of components onto physical devices.
The design of a system is often impacted by the connection delays routed along the programmable interconnect of the target device. The interconnect provides the ability to implement arbitrary connections, however, it includes both highly capacitive and resistive elements. The delay experienced by a connection is affected by the number of routing elements used to route the connection. Traditional approaches for reducing the delay were targeted at improving the automated placement and routing algorithms in the EDA tools. Although some reductions in delay were achieved with these approaches, the approaches were not able to perform further improvements to the system after the placement and routing phases. It is often only after the placement phase and/or routing phase of the FPGA computer automated design (CAD) flow when connection delays power dissipation on the interconnect are fully known.
In addition, traditional approaches of functional decomposition used for improving the synthesis procedure in the CAD flow utilized data structures such as truth tables that were exponential in the number of variables present in a function being decomposed. This required EDA tools to utilize a large amount of memory and to implement algorithms that were slow in nature.
Thus, what is needed is an efficient and effective method and apparatus for performing layout-driven optimizations on FPGAs after the placement phase of the FPGA CAD flow.